package com.cango.student.algorithm;

import org.springframework.format.number.money.CurrencyUnitFormatter;

import java.util.HashMap;
import java.util.Map;

/**
 * 使用Java打印斐波那契数列的三种方法
 * 斐波那契数列（Fibonacci sequence）的定义：斐波那契数列指的是这样一个数列
 * 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........，这个数列从第3项开始，每一项都等于前两项之和。
 */
public class PrintFib {
    //建立一个函数，用于计算数列中的每一项
    public static long fib(long num) {
        //判断：是否是第一个数和第二个数
        if(num == 1 || num == 2) {
            return 1;
        }else {
            //循环调用本函数
            return fib(num - 2) + fib(num - 1);
        }
    }
    private static Map<Long, Long> map = new HashMap<>(100);


    //建立一个函数，用于计算数列中的每一项
    public static long newFib(long num) {
        //判断：是否是第一个数和第二个数
        if(num == 1 || num == 2) {
            return 1;
        }else {
            if (!map.containsKey(num)) {
                long sum = fib(num - 2) + fib(num - 1);
                map.put(num, sum);
            }
            //循环调用本函数
            return map.get(num);
        }
    }

    //主函数（程序入口）
    public static void main(String[] args) {
        long current = System.currentTimeMillis();
        //建立一个for循环，用于打印第一个至第十个数字
        for(int i = 1;i <= 45;i++) {
            //调用函数进行打印
            System.out.print(fib(i) + "\t");
        }
        long diff = System.currentTimeMillis() - current;
        System.out.println();
        System.out.println(diff);

        System.out.println();

        current = System.currentTimeMillis();
        //建立一个for循环，用于打印第一个至第十个数字
        for(int i = 1;i <= 45;i++) {
            //调用函数进行打印
            System.out.print(newFib(i) + "\t");
        }
        diff = System.currentTimeMillis() - current;
        System.out.println();
        System.out.println(diff);
//        int a = 1;
//        int b = 1;
//        for(int i = 1;i <= 10;i++) {
//
//            System.out.print(a + "\t" + b + "\t");
//            a = a + b;
//            b = a + b;
//        }
//
//        System.out.println();
//        //建立一个长度为10的数组用于存放数列中的数
//        int[] arr = new int[10];
//        //先定义数列中的第一个和第二个数
//        arr[0] = 1;
//        arr[1] = 1;
//        //建立一个for循环，打印数组中的元素
//        for(int i = 0;i < arr.length;i++) {
//            //判断：当打印第三个数前，给第三个数赋值
//            if(i > 1) {
//                arr[i] = arr[i - 2] + arr[i - 1];
//            }
//            System.out.print(arr[i] + "\t");
//        }


    }

}
